package cn.orange.ch08_backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * LC491.非递减子序列
 */
public class LC491 {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> trace = new LinkedList<>();
        backtracking(0, nums, trace, ans);
        return ans;
    }

    private void backtracking(int start, int[] nums, LinkedList<Integer> trace, List<List<Integer>> ans) {
        if (trace.size() >= 2) {
            ans.add(new ArrayList<>(trace));
        }
        boolean[] used = new boolean[201];
        for (int i = start; i < nums.length; i++) {
            int num = nums[i];
            if (!trace.isEmpty() && num < trace.getLast() || used[num + 100]) continue;
            trace.add(num);
            used[num + 100] = true;
            backtracking(i + 1, nums, trace, ans);
            trace.removeLast();
        }
    }

    public static void main(String[] args) {
        LC491 alg = new LC491();
        System.out.println(alg.findSubsequences(new int[]{4, 6, 7, 7}));
        System.out.println(alg.findSubsequences(new int[]{4, 4, 3, 2, 1}));
    }
}
